The Turán graph, denoted by ${\displaystyle T(n,r)}$, is a complete multipartite graph; it is formed by partitioning a set of ${\displaystyle n}$ vertices into ${\displaystyle r}$ subsets, with sizes as equal as possible, and then connecting two vertices by an edge if and only if they belong to different subsets. Where ${\displaystyle q}$ and ${\displaystyle s}$ are the quotient and remainder of dividing ${\displaystyle n}$ by ${\displaystyle r}$ (so ${\displaystyle n=qr+s}$), the graph is of the form ${\displaystyle K_{q+1,q+1,\ldots ,q,q}}$, and the number of edges is

${\displaystyle \left(1-{\frac {1}{r}}\right){\frac {n^{2}-s^{2}}{2}}+{s \choose 2}}$.

The graph has ${\displaystyle s}$ subsets of size ${\displaystyle q+1}$, and ${\displaystyle r-s}$ subsets of size ${\displaystyle q}$; each vertex has degree ${\displaystyle n-q-1}$ or ${\displaystyle n-q}$. It is a regular graph if ${\displaystyle n}$ is divisible by ${\displaystyle r}$ (i.e. when ${\displaystyle s=0}$).